class Bit32Trie:
    def __init__(self, level=0):
        self.level = level
        self.children = dict()
        self.cnt = 0

    def insert(self, val):
        root = self
        level = 0
        for i in range(31, -1, -1):
            if val >> i & 1 not in root.children:
                root.children[val >> i & 1] = Bit32Trie(level + 1)
            root = root.children[val >> i & 1]
            root.divisors += 1


class Trie:
    def __init__(self):
        self.children = dict()

    def insert(self,val:str):
        root = self
        for v in val:
            if v not in root.children:
                root.children[v] = Trie()
            root = root.children[v]
        root.s = val


class Trie:
    def __init__(self,n):
        self.nxt = [[0] * 26 for i in range(n + 1)]
        self.exist = [0] * (n + 1)
        self.cnt = 0
    def insert(self,s):
        p = 0
        for v in s:
            idx = ord(v) - ord('a')
            if not self.nxt[p][idx]:
                self.cnt += 1
                self.nxt[p][idx] = self.cnt
            p = self.nxt[p][idx]
        self.exist[p] = 1

    def find(self,s):
        p = 0
        for v in s:
            idx = ord(v) - ord('a')
            if not self.nxt[p][idx]:
                return 0
            p = self.nxt[p][idx]
        return self.exist[p]


